#include <iostream>
using namespace std;
#include <vector>

template <class T>
struct Less // 升序
{
    bool operator()(const T &x1, const T &x2)
    {
        return x1 < x2;
    }
};

void AdjustDown(int arr[], int sz, int i)
{
    Less<int> lessfunc;

    int parent = i;
    int child = 2 * parent + 1;
    while (child < sz)
    {
        // 找出左右孩子中最大的那个
        if (child + 1 < sz && lessfunc(arr[child], arr[child + 1]))
        {
            child++;
        }

        if (lessfunc(arr[parent], arr[child]))
        {
            swap(arr[child], arr[parent]);
            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}
void heap_sort(int arr[], int sz)
{
    // 首先要建立大堆
    for (int i = (sz - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(arr, sz, i); // 从第i个位置开始向下调整
    }

    // 开始排序
    int ret = sz;
    while (ret--)
    {
        swap(arr[0], arr[ret]);
        AdjustDown(arr, ret, 0);
    }
}

void print_sort(int arr[], int sz)
{
    for (int i = 0; i < sz; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}
int main()
{
    int arr[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
    int sz = sizeof(arr) / sizeof(arr[0]);
    print_sort(arr, sz);
    heap_sort(arr, sz);
    print_sort(arr, sz);
    return 0;
}